package problems.daily;

import java.util.Arrays;

/**
 * 1498. 满足条件的子序列数目
 * <p>https://leetcode.cn/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/</p>
 *
 * @author habitplus
 * @since 20:18, 2022/10/15
 */
public class DT1498 {
    final static int N = 100001;
    final static int MOD = (int) 1e9 + 7;

    public int numSubseq(int[] nums, int target) {
        if (nums == null || nums.length < 1) return 0;

        int n = nums.length;
        // 求乘方
        int[] cf = new int[N];
        cf[0] = 1;
        for (int i = 1; i < N; ++i)
            cf[i] = (cf[i - 1] << 1) % MOD;

        // 排序
        Arrays.sort(nums);
        int k;
        int sum;
        int ret = 0;

        for (int i = 0; i < n && nums[i] * 2 <= target; ++i) {
            k = binarySearch(nums, target - nums[i]) - 1;
            sum = k >= i ? cf[k - i] : 0;
            ret = (ret + sum) % MOD;
        }

        return ret;
    }

    /**
     * 找到 nums[i] <= target 的下一个位置
     */
    private int binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length;
        int mid;
        while (low < high) {
            mid = (low + high) / 2;

            if (mid == nums.length) return mid;

            if (nums[mid] > target) high = mid;
            else low = mid + 1;
        }
        return low;
    }
}
